The present invention is directed to a method and apparatus for halftoning images, and more particularly, to the generation of stochastic screens for use in halftoning digital images.
In the digital reproduction of documents, images are conveniently represented as one or more color planes or separations that can be combined at printing to yield a color print. Each image separation is an arrangement of pixels each of which corresponds to a different location of the image and describes the image density at that location. Typically an image separation comprises a raster image which may be described as an of array pixels. Image density typically is described as one level in a number of possible states or levels. Commonly, color documents are formed using one separation describing density for each of a cyan, magenta, yellow and black colorant; although a larger number and/or alternative colorants may also be used.
Most printing systems have the ability to reproduce an image with a small number of levels, most commonly two, although other numbers are possible. On the other hand, common input devices are capable of describing an image with a substantially larger number of gray levels, with 256 levels a commonly selected number, although larger and smaller levels are possible. When more than two levels of density are used in the description of the image, the levels are often termed “gray”, indicating that they vary between a maximum and minimum, and without reference to their actual color. Thus, given an image or a separation in a color image having perhaps 256 possible density levels, a set of binary printer signals must be produced representing the continuous tone scale of the input image. In such arrangements, digital halftoning or screening techniques in which digital input signals to a digital printer are modified prior to printing a hard copy are used such that a digitally printed version of a continuous tone scale image, e.g., a photographic image, creates the illusion of the continuous tone scale of the photographic original.
Typically, digital halftoning or screening techniques control the printing of spots to obtain the illusion of continuous tones based upon a comparison of the required shade of gray with one of a set of predetermined threshold levels. That is, over a given area in an image separation, each pixel in an array of pixels within the area is compared to one of a set of preselected thresholds such as is taught, for example, in U.S. Pat. No. 4,149,194 to Holladay. If the pixel value exceeds the given threshold level (the gray level is darker), a spot is printed. If the gray is not as dark as a given threshold level, a spot is not printed.
One type of screen that has been found to generate nice halftone patterns is a stochastic screen. A stochastic screen produces dots with a random nature, and its halftone patterns can be less visible than structured halftone patterns produced by traditional ordered dither. For most input levels the outputs of stochastic screens have “blue-noise” spatial spectra which provide pleasant appearance. Various methods exist for generating stochastic screens. One method of making a stochastic screen is to start with a stochastic halftone pattern at a certain level, and then use a low-pass filter to find the largest “voids” or “clusters” and reduce them to generate the halftone patterns for the remaining levels, and when all the levels have been visited, a stochastic screen can be generated by combining the halftone patterns of all levels.
Additional information on halftoning systems using a stochastic process known as a blue noise mask can be found in a family of patents to Parker et al., including U.S. Pat. Nos.: 5,111,310; 5,323,247; 5,341,228; 5,477,305; 5,543,941; 5,708,518; 5,726,772. Briefly, a blue noise mask can be generated as follows. Starting at a first gray level with a chosen dot pattern, or “seed”, the process iteratively uses a Fast Fourier Transform (FFT) techniques with a “blue noise” filter to redistribute all spots in dot pattern and eliminate large visual “clumps.” Next, the dot pattern is processed at the next gray level by increasing (or decreasing) certain number of black spots on the previously determined dot pattern (existing black (or white) spots are not moved). The same filtering technique is used to distribute newly added (or subtracted) dots. The above processing is then repeated for all gray levels sequentially. At each step, the width of the blue-noise filter varies by an amount corresponding to the current gray level. The summation of dot patterns for each gray levels is the blue noise mask generated.
Stochastic screens have been shown to provide good image quality in printers that use ink, such as solid ink printers and ink jet printers, which can print isolated dots reliably and accurately. However, when dot positioning is less accurate or reliable, halftone noise can be quite objectionable resulting in a noticeable reduction of image quality. Dot placement error often increases when the firing frequency of the jets increases. As the firing frequency goes up, there is more variation as to where the dots are placed. There are a variety of factors that can contribute to dot positioning errors. For example, inconsistencies and/or contaminants in the ink as well as the use of different inks may vary the flow rate in the print head, cause the ink to foul or clog nozzles in the print head, or change the thermal characteristics of the ink. Each these can result in variations in the amount and the location of ink deposition. Additionally, a variety of manufacturing flaws can impact the rate ink flows through or discharges from the print head; thereby resulting in inconsistent and inaccurate drop placement.
Another factor that contributes to the noise level in stochastic halftoning is the interaction between neighboring dots, which can be quite non-symmetric. For example, for some inks such as many of those with solid ink printers, dots can be congealed in a way that is very difficult to characterize. Even when two dot patterns are geometrically symmetric, they can have different visual effects. Furthermore, inconsistencies and/or contaminants in the ink also impact the way dots congeal as well as dot-to-dot interactions (such as agglomeration); thereby adding further complexity and unpredictability to the process. These printer artifacts, dot positioning errors and unfavorable dot-to-dot interaction, can combine to increase the noise level in stochastic halftoning on certain printers.
Thus, there is a desire to construct a halftone screen which exhibits robustness against printing artifacts such as frequency dependent dot placement and dot-to-dot interactions (such as agglomeration) while maintaining the favorable characteristics of a stochastic screen.